/*
题目: 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

https://leetcode.cn/problems/maximum-length-of-pair-chain
 */
 */
public class FindLongestChain {
    public int findLongestChain(int[][] pairs) {
        public int findLongestChain(int[][] pairs) {
            int row = pairs.length;
            // 最长递增子序列
            Arrays.sort(pairs, new Comparator<int[]> () {
                public int compare(int[] o1, int[] o2) {
                    // 这样子让同一层的元素无法参与 LOS 的计算
                    if (o1[0] == o2[0]) {
                        return o2[1] - o1[1];
                    }
                    return o1[0] - o2[0];
                }
            });

            // 贪心法, 每次都努力让子序列增长的慢一点
            // d 数组下标表示长度为 i 的子序列的最后一个数
            int[] d = new int[row + 1];
            int dLen = 1;
            d[0] = pairs[0][1];
            for (int i = 1; i < row; i++) {
                // 注意这里是0, 新增一层的元素
                if (pairs[i][0] > d[dLen - 1]) { // 如果比最后一个元素还大
                    d[dLen ++] = pairs[i][1];
                } else {
                    // 替换掉第一个比 pairs[i][1] 大的元素
                    int left = 0, right = dLen - 1;
                    while (left <= right) {
                        int mid = left + ((right - left) >> 1);
                        if (d[mid] < pairs[i][1]) {
                            left = mid + 1;
                        } else {
                            right = mid - 1;
                        }
                    }
                    d[right + 1] = pairs[i][1];
                }
            }

            return dLen;
        }


        // 动态规划版
        public int findLongestChainDp(int[][] pairs) {
            int row = pairs.length;
            // 最长递增子序列
            Arrays.sort(pairs, new Comparator<int[]> () {
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] == o2[0]) {
                        return o2[1] - o1[1];
                    }
                    return o1[0] - o2[0];
                }
            });

            int[] dp = new int[row];
            Arrays.fill(dp, 1);
            for (int i = 1; i < row; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[i][0] > pairs[j][1]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[row - 1];
        }
}
